class code4 {
    //无重复 + set去重即可
    Set<String> set;
    boolean[] check;
    public String[] permutation(String s) {
        set = new HashSet<>();
        check = new boolean[s.length()];
        StringBuffer ss = new StringBuffer();
        dfs(ss,s);
        return set.toArray(new String[set.size()]);
    }

    public void dfs(StringBuffer ss,String s) {
        //出口
        if(ss.length() == s.length()) {
            set.add(ss.toString());
            return;
        }

        for(int i=0;i<s.length();i++) {
            if(!check[i]) {
                check[i] = true;
                ss.append(s.charAt(i));
                dfs(ss,s);
                //回溯
                ss.deleteCharAt(ss.length()-1);
                check[i] = false;
            }
        }
    }
}